// Package day_12_dp 10-64
// @Title day_12_dp
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/7 9:45
// @Create  2021/9/7 9:45
package day_12_dp

func min1(a, b int) int {
	if a > b {
		return b
	}
	return a
}
func MinPathSum(grid [][]int) int {
	n := len(grid)
	m := len(grid[0])
	dp := make([][]int, n)

	sum := 0
	// 初始化DP数组的第一列
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		sum += grid[i][0]
		dp[i][0] = sum
	}
	// 初始化DP数组的第一行
	row := 0
	for i := 0; i < m; i++ {
		row += grid[0][i]
		dp[0][i] = row
	}
	// DP数组从第一行第一列开始遍历
	for i := 1; i < n; i++ {
		for j := 1; j < m; j++ {
			dp[i][j] = min1(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
		}
	}
	return dp[n-1][m-1]
}
